vector <oint> fact_mod_saved;
oint fact_mod(int n, int mod) 
{
	if (fact_mod_saved[n] != -1)
		return fact_mod_saved[n];
	oint result = 1;
	while (n > 1) 
	{
		result = (result * ( ((n / mod) % 2 != 0) ? mod - 1 : 1)) % mod;
		for (int i = 2; i <= n % mod; ++i)
			result = (result * i) % mod;
		n /= mod;
	}
	return fact_mod_saved[n] = result % mod;
}